package Hot100.Medium.GreedyAndDP.DynamicPlanning.Rob;



import Hot100.Easy.LC94.TreeNode;

import java.util.HashMap;
import java.util.Map;

public class LC337_RobInTree {
    public int rob(TreeNode root) {
        Map<TreeNode, Integer> memo = new HashMap<>();
        return robAction(root, memo);
    }

    int robAction(TreeNode root, Map<TreeNode, Integer> memo) {
        if (root == null)
            return 0;
        // 如果当前节点之前遍历过，直接从Map里取出来，降低时间复杂度
        if (memo.containsKey(root))
            return memo.get(root);
        int money = root.val;
        // 偷目前的node，因此只能偷其孙子节点
        if (root.left != null) {
            money += robAction(root.left.left, memo) + robAction(root.left.right, memo);
        }
        if (root.right != null) {
            money += robAction(root.right.left, memo) + robAction(root.right.right, memo);
        }
        // 不偷当前节点，因此偷其儿子节点
        int sonMoney = robAction(root.left, memo) + robAction(root.right, memo);
        // 到每个节点时，都记录一下偷与不偷该节点的偷到钱的最大值
        int res = Math.max(money, sonMoney);
        memo.put(root, res);
        return res;
    }
}
